package com.example.stack;

/**
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈
 * 解法:
 * 使用两个栈:主栈记录所有数据,副栈负责记录到当前压栈的元素的最小值
 *
 *
 * 细节问题:
 * 1.使用单链表实现两个栈
 *
 * 2.每次压栈时要判断当前压栈的值是否小于副栈栈顶的值
 *    小于时将当前这个值也要压入副栈
 *    不小于则将副栈栈顶元素再压一次进入副栈
 */
public class Leecode155_MinStack {
    // 存储所有数据的栈
    private final Node stackHead;
    // 存储当前栈中最小的值的栈(每次主栈压栈时都得将当前最小值压一次栈)
    private final Node minStack;
    private int size;

    public static void main(String[] args) {

        Leecode155_MinStack stack = new Leecode155_MinStack();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        System.out.println(stack.getMin());
        stack.pop();
        System.out.println(stack.top());
        System.out.println(stack.getMin());


    }

    public Leecode155_MinStack() {
        stackHead = new Node(Integer.MIN_VALUE);
        minStack = new Node(Integer.MAX_VALUE);
        size = 0;
    }

    public void push(int x) {
        // 当要入栈的数比最小栈的栈顶值小，则要将当前这个数压栈到最小栈中
        if (size >= 1) {
            if (x < minStack.next.val) {
                Node minTmp = new Node(x);
                minTmp.next = minStack.next;
                minStack.next = minTmp;
            } else {
                Node minTmp = new Node(minStack.next.val);
                minTmp.next = minStack.next;
                minStack.next = minTmp;
            }
            // size=0时,直接将数据插入压入最小值栈
        } else {
            Node minTmp = new Node(x);
            minTmp.next = minStack.next;
            minStack.next = minTmp;
        }
        Node tmp = new Node(x);
        tmp.next = stackHead.next;
        stackHead.next = tmp;
        ++size;
    }
    public void pop() {
        if (--size >= 0) {
            int tmp = stackHead.next.val;
            stackHead.next = stackHead.next.next;
            minStack.next = minStack.next.next;
        }
    }
    public int top() {
        if (size > 0) {
            return stackHead.next.val;
        }
        return Integer.MIN_VALUE;
    }
    public int getMin() {
        if (size > 0){
            return this.minStack.next.val;
        }
        return Integer.MIN_VALUE;
    }

    private class Node {
        int val;
        Node next;
        public Node(int val) {
            this.val = val;
        }
    }
}
